package com.example.algorithm.no0198.solution;

import com.example.algorithm.no0198.Solution;

/**
 * @Description 动态规划
 * 时间复杂度 O(N) ： 遍历 nums 需要线性时间；
 * 空间复杂度 O(N) ： 需要存储整个数组的结果。
 * @ClassName DpSolution
 * @Author Administrator
 * @Date 2020/5/16 12:48
 * @Version 1.0.0
 */
public class DpSolutionImpl implements Solution {

    /**
     * {1,2,3,1}   4
     *
     * @param nums {1,2,3,1}
     */
    @Override
    public int rob(int[] nums) {

        if (nums == null || nums.length == 0) {
            return 0;
        }

        int size = nums.length;
        if (size == 1) {
            return nums[0];
        }

        int[] res = new int[size];
        res[0] = nums[0];
        res[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < size; i++) {
            res[i] = Math.max(res[i - 1], res[i - 2] + nums[i]);
        }

        return res[size - 1];
    }
}
